(*
  Copyright (c) 2009 Barry Schwartz

  Permission is hereby granted, free of charge, to any person
  obtaining a copy of this software and associated documentation
  files (the "Software"), to deal in the Software without
  restriction, including without limitation the rights to use,
  copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the
  Software is furnished to do so, subject to the following
  conditions:

  The above copyright notice and this permission notice shall be
  included in all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  OTHER DEALINGS IN THE SOFTWARE.
*)

open XNum
  
type ('graph, 'aux, 'solution) update_solution =
  'graph ->
    'solution list ->
      'aux ->
        int -> int -> 'solution list -> (('solution list) * ('aux option))

type 'graph is_forced = 'graph -> int -> bool

type ('graph, 'solution, 'result) compute_path =
  'graph -> ('solution list) array -> 'result

(* |find_shortest_path <update-solutions> <is-forced> <compute-path>
   <initial-solution> <graph> <num-vertices>|

   computes the shortest path in a graph with <num-vertices> vertices
   from the first vertex to the last one. It is assumed that the graph
   is directed with an edge between <i> and <k> iff |i < k|. For each
   vertex <i>, a list of possible shortest paths from the first vertex
   to <i> is computed.

   |update_solution <graph> <previous-solutions> <aux> <previous>
   <current> <current-solutions>|

   updates the solutions of the <current> vertex by adding possible paths
   from the <previous> vertex.

   |is_forced <graph> <i>| should return |True| if any path is forced to
   visit vertex <i>. If <i> might be skipped it returns |False|.

   |compute_path <graph> <solutions>| computes the resulting shortest
   path from the array of partial solutions. Usually, it will select
   one element of the list |solutions.(num-vertices - 1)|.

   <initial_solution> is the data associated to the path from the first
   vertex to itself.

   <graph> contains data associated with the graph.

   <num_vertices> is the number of vertices of <graph>.
*)
let find_shortest_path update_solution is_forced compute_path initial_solution initial_data graph num_vertices =

  let solutions = Array.make num_vertices [] in

  let aux_data = Array.make num_vertices (Some initial_data) in

    solutions.(0) <- [initial_solution];

    (* Compute all shortest paths from the first vertex to vertex <current>. *)
    let rec fill_array current =
      if current >= num_vertices then
        compute_path graph solutions
      else
        iter_active (current - 1) current

    and fill_next_vertex current =
      (* Mark the current vertex as inactive if we have found no
         solutions. *)
      begin
        match solutions.(current) with
          | [] -> aux_data.(current) <- None
          | _ -> ()
      end;
      fill_array (current + 1)

    and iter_active prev current =
      if prev < 0 then
        begin
          (* Mark the current vertex as inactive if we have found no
             solutions. *)
          begin
            match solutions.(current) with
              | [] -> aux_data.(current) <- None
              | _ -> ()
          end;
          fill_next_vertex current
        end
      else
        match aux_data.(prev) with
          | None -> iter_active (prev - 1) current
          | Some aux -> process_active_vertex aux prev current

    and process_active_vertex aux previous current =
      (* Consider the edge from <previous> to <current>. *)
      let (new_sol, new_aux) = update_solution graph solutions.(previous) aux previous current solutions.(current) in
        (solutions.(current) <- new_sol;
         aux_data.(previous) <- new_aux;
         if is_forced graph previous then (* Do not scan over a forced vertex. *)
           fill_next_vertex current
         else
           iter_active (previous - 1) current)
    in
      fill_array 1
  

